package com.monotoneStack;

import java.util.Arrays;
import java.util.Stack;

/**
 * 下一个更大元素 II
 *
 * 输入: nums = [1,2,1]
 * 输出: [2,-1,2]
 * 解释: 第一个 1 的下一个更大的数是 2；
 * 数字 2 找不到下一个更大的数；
 * 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
 *
 */
public class NextGreaterElementII0121_503 {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[nums.length];
        Arrays.fill(res,-1);

        stack.push(0);
        for (int i = 1; i < 2 * nums.length; i++) {
            int index = i%nums.length;
            if(nums[index] <= nums[stack.peek()]){
                stack.push(index);
            }else {
                while (!stack.isEmpty() && nums[index]>nums[stack.peek()]){
                    res[stack.peek()] = nums[index];
                    stack.pop();
                }
                stack.push(index);
            }
        }
        return res;
    }
}
